package com.zxy.leetcode.lcci;

/**
 * https://leetcode-cn.com/problems/contiguous-sequence-lcci/
 *
 * 连续数列
 * 给定一个整数数组，找出总和最大的连续数列，并返回总和。
 *
 * 本题最优解法是动态规划，但题目要求用分治算法来解答
 *
 * 分治算法的思路
 * 我们把数组分割成两边，那么结果出现的区域，完全在左边、完全在右边、包括中间两个节点的左右两部分
 */
public class Test1617 {

    public static void main(String[] args) {
        Test1617 test = new Test1617();

        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(test.maxSubArray(nums)); // 6 {4,-1,2,1}
    }

    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        return divide(nums, 0,nums.length-1);
    }

    private int divide(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int mid = (left + right) >> 1;
        // 1.左边最大的子序列
        int leftMaxSum = divide(nums, left, mid);
        // 2.右边最大的子序列
        int rightMaxSum = divide(nums, mid+1, right);

        // 3.最大数列和在中间
        // 包括中间的，左边部分最大
        int sum = nums[mid];
        int leftMidSum = sum;
        for (int i=mid-1; i>=left; i--) {
            sum += nums[i];
            leftMidSum = Math.max(leftMidSum, sum);
        }

        // 包括中间的，右边部分最大
        sum = nums[mid+1];
        int midRightSum = sum;
        for (int i=mid+2; i<=right; i++) {
            sum += nums[i];
            midRightSum = Math.max(midRightSum, sum);
        }

        return Math.max(Math.max(leftMaxSum, rightMaxSum), leftMidSum+midRightSum);
    }

}
